The integrity of communication has two components. One is the maintenance of privacy or confidentiality of the message or information being communicated; the other is the ability to authenticate the source of the message. The former of these is discussed hereinafter. Here we mention some of the methods which have been used to verify the message source in private key systems.
One of the simplest ways of authenticating the source is for the sender and receiver to prearrange a short list of valid messages, with the understanding that any alteration to one of these would indicate that an interception has taken place or a false message has been sent. A variation on this is to pre-determine the message structure and only accept as authentic those messages which fit this structure. Where authentication of the source is particularly important under the above arrangement, arbitration can be introduced to determine, usually in probabilistic terms, the level of certainty with which a message can be connected to its source. For comprehensive and clear expositions on authentication and arbitration, the reader is referred to (20) and (21). For recent work on codes supplying both secrecy and authentication, see (18), (21)-(25) and (27).
`Signing` a message is a particular kind of authentication method. A person's name or digital `fingerprint` are examples of a signature. If a signature is incorporated as part of the message being sent, it is as vulnerable to change by an opponent as any other part of the message. In contradiction to this perception, we present in this patent application a protocol for a secure private key system with signature.
We mention finally that many signature schemes have been based on `data compression` or `hashing` eg. (19), reducing the message to a miniature version of itself, which then essentially plays the role of the signature.
The following prior art disclosed information in the general field of the present invention but one discloses information which is material to the present invention.
(1) S. Ball, On the size of a triple blocking set in PG(2,q), European Journal of Combinatorics, 17 (1996), 427-435. PA1 (2) S. Ball, Multiple blocking sets and arcs in finite planes, preprint. PA1 (3) S. Ball and A. Blokhuis, On the size of a double blocking set in PG(2,q), preprint. PA1 (4) L. M. Batten, Combinatorics of Finite Geometrics, Cambridge University Press, 1986. PA1 (5) L. M. Batten, Blocking sets in designs, Congressus Numerantium, 99 (1994), 139-154 PA1 (6) H. Beker and F. C. Piper, Cipher Systems: The Protection of Communications, John Wiley & Son, 1982. PA1 (7) L. Berardi and F. Eugeni, Blocking sets in affine planes, J. Geom., 22 (1984), 167-177 PA1 (8) Th. Beth, D. Jungnickel and H. Lenz, Design Theory, Bibliographisches Institut, Zurich, 1985. PA1 (9) A. E. Brouwer and A. Schrijver, The blocking number of an affine space, J. Comb. Theory, 24 (1978), 251-253 PA1 (10) A. A. Bruen and R. Silverman, Arcs and blocking sets II, Europ. J. Comb., 8 (1987), 351-356. PA1 (11) C. Delany, COMPLETE--Rationale and User's guide, Technical Report, CCR-01-95, Centre for Combinatorics, University of Queensland, 1995. PA1 (12) H. m. Gustafson, A. N. Pettitt, E. P. Dawson and L. J. O'Connor, Linear dependencies in product ciphers, Austral. J. Comb., 10 (1994), 115-129. PA1 (13) J. W. P. Hirschfeld, Projective Geometrics over Finite Fields, Clarendon Press, Oxford, 1979. PA1 (14) R. E. Jamison, Covering finite fields with cosets of subspaces, J. Comb. Theory (A), 22 (1977) 253-266. PA1 (15) A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Press, 1993. PA1 (16) A. Nijenhuis and H. S. Wilf, Combinatorial Algorithms. 2nd ed'n., Academic Press, 1978. PA1 (17) C. Ramsay, An improved version of COMPLETE for .lambda.=1, Technical Report, CCR-03-96, Centre for Combinatorics, University of Queensland, 1996. PA1 (18) R. S. Rees and D. R. Stinson, Combinatorial characterizations of authentication codes II, Designs, Codes and Cryptography, 7 (1996), 239-259. PA1 (19) B. Schneier, Applied Cryptography, John Wiley & Son, 1994. PA1 (20) J. Seberry and J. Pieprzyk, Cryptography: An Introduction to Computer Security, Prentice Hall, 1989. PA1 (21) G. J. Simmons, A cartesian product construction for unconditionally secure authentication codes that permit arbitration, J. Cryptology, 2 (1990), 77-104. PA1 (22) D. R. Stinson, Some constructions and bounds for authentication codes, J. Cryptology 1 (1988). 37-51 PA1 (23) D. R. Stinson, A construction for authentication/secrecy codes from certain combinatorial designs, J. Cryptology, 1 (1988), 119-127. PA1 (24) D. R. Stinson, The combinatorics of authenticationand secrecy codes, J. Cryptology, 2 (1990), 23-49. PA1 (25) D. R. Stinson, Combinatorial characterizations of authentication codes, J. Cryptology, 2 (1990), 175-187. PA1 (26) D. R. Stinson, Cryptography: Theory and Practice, CRC Press, 1995. PA1 (27) T. van Trung, On the construction of authentication and secrecy codes, Designs, Codes and Cryptology, 5 (1995), 269-280. PA1 (28) H. S. Wilf, Combinatorial Algorithms: An Update, SIAM, 1989. PA1 (29) I. Anderson, Combinatorics of Finite Sets, Oxford Science Publications. PA1 (30) M. De Brandes and V. Rodl, (1984), `Steiner Triple Systems with small maximal independent sets` Ars Comb. 17 (1987) 15-19. PA1 (31) A. Bruen `Baer subplanes and blocking sets`, Bull. Amer. Math. Soc. 76 (1970), 342-344 PA1 (32) G. B. Dantizig and A. J. Hoffman, `Dilworth's theorem on partially ordered sets` in Linear Inequalities and Related Systems, Annals of Math Studies no. 38, (Ed. Kuhn and Tucker) (1956), 207-214. PA1 (33) R. P. Dilworth, `A decomposition theorem for partially ordered sets`. Ann. Math. 51 (1950), 161-165. PA1 (34) K. Phelps and V. Rodl, "Steiner Triple Systems with minimum independence number". Ars Comb. 21 (1986) 167-172. PA1 (35) V. Pless, Introduction to the theory of error-correcting codes, John Wiley and Sons, New York, Toronto, 1982. PA1 (36) E. Sperner, `Ein Satz Uber Untermengen einer endlichen Menge.` Math. Z. 27 (1928), 544-548. PA1 providing to the authorized sites a set of messages which can be transmitted between the sites, each message being a string of bits in identifiable positions, and each message being allocated an agreed meaning; PA1 communicating to the authorized sites information identifying for the set of messages selected positions of the bits so that others of the positions of the bits are not selected, the selection of positions being arranged to allow determination of a unique message from the messages set by analysis of the bits in said selected positions; PA1 providing to the authorized sites a secrete encryption key and a corresponding secret decryption key such that the secrete encryption key is known to said transmission site and the corresponding decryption key is known to said receiving site; PA1 providing to said transmission site a second encryption key different from said secret encryption key; PA1 selecting from the set of messages a subset of messages to be transmitted; PA1 at the transmission site encrypting for the subset of messages, using said private encryption key, only the bits at the selected positions; PA1 at the transmission site encrypting for the subset of messages, using said second encryption key, the bits at the not selected positions; PA1 transmitting the encrypted subset of messages from the transmission site; PA1 at the receiving site for each message of the subset decrypting the message using the decryption key to decrypt the bits at said selected positions; PA1 at the receiving site for each message of the subset analyzing the decrypted bits at said positions to determine each message from the set of messages; PA1 and providing a signature of the transmitting site by comparing, for at least some messages, the encrypted bits at the not selected positions with the bits at the not selected positions from the set of messages.
Some of the above prior art documents are variously mentioned in the following description of the present invention where they are defined by the relevant reference numeral, as for example [21]. Where so mentioned, the disclosure of the defined prior art document is incorporated into this description by reference.